home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / Libraries / VideoToolbox 95.04.18 / VideoToolboxSources / NoisePdfFill.c < prev    next >
Encoding:
Text File  |  1995-04-18  |  15.8 KB  |  418 lines  |  [TEXT/MMCC]
  1. /*
  2. NoisePdfFill.c
  3.  
  4. error=NoisePdfFill(world,&rect,pdfKind,&mean,&sd,min,max);
  5. error=NoisePdfAdd(world,&rect,pdfKind,&mean,&sd,min,max);
  6.  
  7. Generate good noise images quickly. You supply a GWorld (or a window) and a rect
  8. indicating how much of it to fill with noise. "world" may be a pointer to a
  9. GWorld, a color CWindow, or, with casting, a plain-old Window. NoisePdfFill fills
  10. the pixels within rect with noise; NoisePdfAdd adds noise to them. Each pixel
  11. will get an independent integer sample from a specified probability density
  12. function (pdf): kBinaryPdf, kUniformPdf, or kGaussianPdf. (A fourth pdf,
  13. kBinomialPdf, is not recommended.) You specify the pdf kind, mean, and
  14. "unclipped" standard deviation. The last two arguments, "min" and "max", are used
  15. to clip, i.e. restrict the range of the pdf (e.g. to preclude overflow in your
  16. image pixels). In the cases of kUniformPdf, kBinomialPdf, and kGaussianPdf,
  17. samples falling outside the range [min,max] are discarded and replaced by
  18. independent new samples. In the case of kBinary, each sample has one of only two
  19. values, with equal probability; these two values are initially set to mean±sd, to
  20. yield the desired mean and sd, but they are adjusted, if necessary, to bring them
  21. within the range [min,max]. Upon return, the mean and sd arguments (which are
  22. passed by reference, i.e. by address, not by value) return the mean and standard
  23. deviation of the random generator of the samples (i.e. the clipped pdf).
  24.  
  25. The requested standard deviation, sd, must be greater than or equal to zero. The
  26. special case of zero standard deviation is recognized and performed quickly,
  27. producing a uniform image with specified mean. A request for an unachievably low,
  28. but nonzero, sd will be served by providing the lowest achievable sd (given the
  29. specified min and max), on the premis that the user cares most about log sd, so
  30. that the least possible nonzero sd will be a better approximation to an
  31. unachievably low sd than would zero sd. Supplying an sd of INF will produce
  32. samples with values of min and max if the pdf kind is kBinaryPdf, and will
  33. produce a uniform distribution over the range [min,max] if the pdf is
  34. kUniformPdf, kGaussianPdf, or kBinomialPdf.
  35.  
  36. "max" must be greater than or equal to "mean", which must be greater than or
  37. equal to "min". Normally, image pixels are considered positive and you'll want to
  38. make "min" greater than or equal to zero, but this is not enforced by
  39. NoisePdfFill; e.g. you can add zero-mean noise to a positive image. 
  40.  
  41. Calling NoisePdfAdd with a "min"<0 should work perfectly (though it hasn't been
  42. tested), but may be significantly slower than when "min"≥0. NoisePdfAdd() uses
  43. NoisePdfFill() to make the noise in a temporary new GWorld and then calls
  44. CopyWindows to add the noise to your image. If "min"≥0 then NoisePdfAdd() uses a
  45. fast parallel addition that assumes there will be no overflow in each pixel's
  46. arithmetic, so the user should take care to specify a "max" that will indeed
  47. prevent overflow, since any overflow would affect a neighboring pixel. If "min"<0
  48. then the unsigned addition of "negative" with positive pixels to produce positive
  49. pixels will "overflow" in the normal course of computing the sum using unsigned
  50. arithmetic. The bits of the pixel itself will be correct, but the overflow would
  51. affect a neighboring pixel if parallel addition were used, so the additions are
  52. done independently, one pixel at a time, which takes longer.
  53.  
  54. kBinaryPdf, kUniformPdf, and kGaussianPdf should all be useful. We use
  55. kGaussianPdf in most of our noise-masking work, but for dynamic noise we
  56. sometimes use kBinaryPdf in order to achieve more noise power, assuming that the
  57. observer will visually integrate several of the dynamic frames, blurring the
  58. distinction between pdf's. Presumably the three kinds of noise would be visually
  59. indistinguishable if shown with independent 15 ms frames and equal sd.
  60.  
  61. kBinomialPdf works fine, but is not recommended. The kBinomialPdf code uses the
  62. fact that the number of heads in 24 coin tosses is approximately gaussian. This
  63. code was originally written as a quick way to make approximately gaussian noise.
  64. However, kBinomialPdf is probably much slower than the subsequently written
  65. kGaussianPdf, which provides samples that are accurately gaussian.
  66.  
  67. void GetGoodNoisePdfBounds(pdfKind,mean,clippedSd,&unclippedSd,&min,&max);
  68.  
  69. GetGoodNoisePdfBounds is a utility routine that helps you choose good parameters
  70. with which to call NoisePdfFill or NoisePdfAdd. Be aware that, whereas
  71. NoisePdfFill and NoisePdfAdd are general-purpose, the "good" in the name
  72. "GetGoodNoisePdfBounds" indicates that its recommendations are not necessarily
  73. best. It incorporates several reasonable but somewhat arbitrary assumptions, e.g.
  74. that you'd like to clip your gaussian at ±2 sd, and helps you to choose a good
  75. set of parameters to obtain that result. GetGoodNoisePdfBounds will not be
  76. appropriate to all uses of NoisePdfFill and NoisePdfAdd; you may want to write
  77. your own. Note: GetGoodNoisePdfBounds is still under development; I haven't yet
  78. added its prototype to VideoToolbox.h.
  79.  
  80. The hardest part of writing the code in this file was figuring out how to
  81. separate the general-purpose code (i.e. NoisePdfFill) from the pragmatic but
  82. somewhat arbitrary assumptions now encapsulated in GetGoodNoisePdfBounds.
  83.  
  84. HISTORY:
  85. 3/20/95 dgp wrote it, based on my MakeTextInNoiseWorld.c
  86. 4/8/95 dgp removed any assumption that world is a GWorldPtr; it can also
  87. be a CWindowPtr or a WindowPtr.
  88. 4/18/95 dgp fixed error in NoisePdfAdd: mean & sd were swapped.
  89. */
  90.  
  91. #include "VideoToolbox.h"
  92. #include <assert.h>
  93. #include <math.h>
  94. OSErr NoisePdfFill(GWorldPtr world,Rect *rectPtr
  95.     ,int pdfKind,double *meanPtr,double *sdPtr,int min,int max);
  96. OSErr NoisePdfAdd(GWorldPtr world,Rect *rectPtr
  97.     ,int pdfKind,double *meanPtr,double *sdPtr,int min,int max);
  98. void GetGoodNoisePdfBounds(int pdfKind,double mean,double clippedSd
  99.     ,double *unclippedSdPtr,int *minPtr,int *maxPtr);
  100.  
  101. //enum{kBinaryPdf=0,kBinomialPdf,kGaussianPdf,kUniformPdf}; // in VideoToolbox.h
  102.  
  103. #undef MAX
  104. #undef MIN
  105. #define MAX(a,b) ((a) > (b) ? (a) : (b))
  106. #define MIN(a,b) ((a) < (b) ? (a) : (b))
  107. static Boolean diagnostics=0;
  108.  
  109. OSErr NoisePdfFill(GWorldPtr world,Rect *rectPtr
  110.     ,int pdfKind,double *meanPtr,double *sdPtr,int min,int max)
  111. {
  112.     CGrafPtr oldPort;
  113.     GDHandle oldDevice;
  114.     int error=0;
  115.     OSErr osErr=0;
  116.     long n;
  117.     int i,j,x,y;
  118.     long low,high,sample;
  119.     double actualMean,actualSd;    // mean and sd of process that generated the image
  120.     long actualMin,actualMax;
  121.     int binomialSamples;
  122.     double binomialFactor;
  123.     long extraSamples;
  124.     short *distribution;
  125.     static short **distributionHandle=NULL;
  126.     static long distributionSize;
  127.     static double lowSave,highSave,meanSave,unclippedSdSave,actualSdSave;
  128.     double meanSquare,a,aa;
  129.     RGBColor rgb;
  130.     GDHandle device;
  131.     int pixelSize;
  132.     static const RGBColor blackRGB={0,0,0},whiteRGB={0xFFFF,0xFFFF,0xFFFF};
  133.     unsigned long pix[2048];
  134.     register long *pL;
  135.     
  136.     // Make noise. Takes 300 ms
  137.     assert(StackSpace()>4000);
  138.     assert(world!=NULL && sdPtr!=NULL && meanPtr!=NULL);
  139.     assert(!IsNan(*meanPtr) && !IsNan(*sdPtr));
  140.     assert(*sdPtr>=0.0);
  141.     assert(min<=*meanPtr && *meanPtr<=max);
  142.     high=max;
  143.     low=min;
  144.     if(IsInf(*sdPtr) && pdfKind!=kBinaryPdf)pdfKind=kUniformPdf;
  145.     switch(pdfKind){
  146.     case kBinaryPdf:
  147.         // high and low are values corresponding to heads and tails.
  148.         // The high-low difference is more important than their individual values.
  149.         if(!IsInf(*sdPtr)){
  150.             a=2*(*sdPtr);
  151.             low=MAX(floor(0.5+*meanPtr-a/2),min);
  152.             high=MIN(floor(0.5+low+a),max);
  153.             low=MAX(floor(0.5+high-a),min);
  154.             if(low==high && *sdPtr>0){
  155.                 if(high<max)high++;
  156.                 else if(low>min)low--;
  157.             }
  158.         }
  159.         break;
  160.     case kUniformPdf:
  161.         if(!IsInf(*sdPtr)){
  162.             a=2*sqrt(3)*(*sdPtr)-1;    // integer range of pdf for specified sd
  163.             low=MAX(floor(0.5+*meanPtr-a/2),min);
  164.             high=MIN(floor(0.5+low+a),max);
  165.             low=MAX(floor(0.5+high-a),min);
  166.             if(low==high && *sdPtr>0){
  167.                 if(high<max)high++;
  168.                 else if(low>min)low--;
  169.             }
  170.         }
  171.         break;
  172.     default:
  173.         break;
  174.     }
  175.     GetGWorld(&oldPort,&oldDevice);
  176.     device=GetWindowDevice((WindowPtr)world);
  177.     pixelSize=(**(**device).gdPMap).pixelSize;
  178.     if(low==high){
  179.         SetGWorld(world,device);
  180.         Index2Color(low,&rgb);
  181.         RGBBackColor(&rgb);
  182.         EraseRect(rectPtr);
  183.         SetGWorld(oldPort,oldDevice);
  184.         actualMean=low;
  185.         actualSd=0;
  186.         goto done;
  187.     }
  188.     switch(pdfKind){
  189.     case kBinaryPdf:
  190.         SetGWorld(world,device);
  191.         Index2Color(low,&rgb);
  192.         RGBBackColor(&rgb);
  193.         Index2Color(high,&rgb);
  194.         RGBForeColor(&rgb);
  195.         error=NoiseFill(world,rectPtr,1,1,0); 
  196.         RGBBackColor(&whiteRGB);
  197.         RGBForeColor(&blackRGB);
  198.         SetGWorld(oldPort,oldDevice);
  199.         actualSd=0.5*(high-low);
  200.         actualMean=0.5*(high+low);
  201.         break;
  202.     case kUniformPdf:
  203.         n=1+high-low;
  204.         assert(rectPtr->right-rectPtr->left<=sizeof(pix)/sizeof(*pix));
  205.         for(y=rectPtr->top;y<rectPtr->bottom;y++){
  206.             pL=(long *)pix;
  207.             for(x=rectPtr->right-rectPtr->left-1;x>=0;x--)
  208.                 *pL++=low+nrand(n);
  209.             SetWindowPixelsQuickly((WindowPtr)world,rectPtr->left,y
  210.                 ,pix,rectPtr->right-rectPtr->left);
  211.         }
  212.         assert(n<=sizeof(pix)/sizeof(*pL));
  213.         pL=(long *)pix;
  214.         for(x=low;x<=high;x++)*pL++=x;
  215.         actualMean=MeanL((long *)pix,1+high-low,&actualSd);
  216.         if(diagnostics)printf("unclippedSd %f, actualSd %f, actualSd/unclippedSd %f\n"
  217.             ,*sdPtr,actualSd,actualSd/(*sdPtr));
  218.         break;
  219.     case kGaussianPdf:
  220.         /*
  221.         First we make an ordered list of about twenty thousand integers, with 
  222.         frequency proportional to the desired probability. This table only needs
  223.         to be made once and can be reused indefinitely, until the parameters  
  224.         (mean, sd, min, max) of the distribution change. Each noise pixel is
  225.         a random sample from the table.
  226.         */
  227.         if(distributionHandle==NULL || low!=lowSave || high!=highSave 
  228.             || IsInf(*sdPtr)!=IsInf(unclippedSdSave)
  229.             || (!IsInf(*sdPtr) && fabs(*sdPtr/unclippedSdSave-1)>.01)
  230.             || *meanPtr!=meanSave){
  231.             distributionSize=256*100L;
  232.             if(distributionHandle==NULL){
  233.                 distributionHandle=(short **)TempNewHandle(distributionSize*sizeof(*distribution),&osErr);
  234.                 error=osErr;
  235.                 if(distributionHandle==NULL){
  236.                     distributionHandle=(short **)NewHandle(distributionSize*sizeof(*distribution));
  237.                     error=MemError();
  238.                 }else error=0;
  239.                 if(distributionHandle==NULL)PrintfExit("Sorry, couldn't allocate %ld bytes "
  240.                     "for a gaussian table. File “%s” line %d.\n"
  241.                     ,distributionSize*sizeof(*distribution),__FILE__,__LINE__);
  242.             }
  243.             if(fabs((high-*meanPtr)-(highSave-meanSave))>0.5 || high-low!=highSave-lowSave 
  244.                 || IsInf(*sdPtr)!=IsInf(unclippedSdSave)
  245.                 || (!IsInf(*sdPtr) && fabs(*sdPtr/unclippedSdSave-1)>.01)){
  246.                 // takes 300 ms
  247.                 BoundedNormalIntegers(*distributionHandle,distributionSize
  248.                     ,*meanPtr,*sdPtr,low,high);
  249.             }else{
  250.                 j=floor(0.5+*meanPtr-meanSave);
  251.                 distribution=*distributionHandle;
  252.                 if(j!=0)for(i=0;i<distributionSize;i++)distribution[i]+=j;
  253.                 *meanPtr=meanSave+j;
  254.             }
  255.             lowSave=low;
  256.             highSave=high;
  257.             unclippedSdSave=*sdPtr;
  258.             meanSave=*meanPtr;
  259.             actualMean=MeanW(*distributionHandle,distributionSize,&actualSdSave);
  260.         }
  261.         actualSd=actualSdSave;
  262.         assert(rectPtr->right-rectPtr->left<=sizeof(pix)/sizeof(*pix));
  263.         //HLock((Handle)distributionHandle);
  264.         distribution=*distributionHandle;
  265.         for(y=rectPtr->top;y<rectPtr->bottom;y++){
  266.             pL=(long *)pix;
  267.             for(x=rectPtr->right-rectPtr->left-1;x>=0;x--)
  268.                 *pL++=distribution[nrand(distributionSize)];
  269.             SetWindowPixelsQuickly((WindowPtr)world,rectPtr->left,y
  270.                 ,pix,rectPtr->right-rectPtr->left);
  271.         }
  272.         if(diagnostics)printf("unclippedSd %f, actualSd %f, actualSd/unclippedSd %f\n"
  273.             ,*sdPtr,actualSd,actualSd/(*sdPtr));
  274.         break;
  275.     case kBinomialPdf:
  276.         // Use the number of heads in 24 coin flips as a random variable.
  277.         // It can be computed quickly and is approximately normal.
  278.         // Shift and scale to obtain the specified mean and variance.
  279.         // Discard samples outside the range [min,max].
  280.         // Return mean and sd of the clipped distribution.
  281.         binomialSamples=24;    // should be even (for integer divide by 2)
  282.         binomialFactor=*sdPtr/sqrt(binomialSamples*0.25);
  283.         /*
  284.         The empirical approach of actually measuring the mean and variance
  285.         of our noise generator demands that we produce a
  286.         reasonable number of samples, at least 1000. Any extra samples are later
  287.         discarded.
  288.         */
  289.         assert(rectPtr->right-rectPtr->left<=sizeof(pix)/sizeof(*pix));
  290.         extraSamples=ceil(1000.0/(rectPtr->bottom-rectPtr->top))
  291.             -(rectPtr->right-rectPtr->left);
  292.         if(extraSamples<0)extraSamples=0;
  293.         a=aa=0.0;
  294.         n=0;
  295.         for(y=rectPtr->top; y<rectPtr->bottom; y++){
  296.             pL=(long *)pix;
  297.             for(x=rectPtr->right-rectPtr->left-1; x>=-extraSamples; x--){
  298.                 do{
  299.                     sample=floor(0.5+*meanPtr+binomialFactor
  300.                         *(BinomialSampleQuickly(binomialSamples)-binomialSamples/2));
  301.                 }while(sample<low || sample>high);
  302.                 a+=sample;
  303.                 aa+=(long)sample*(long)sample;
  304.                 n++;
  305.                 if(x>=0)*pL++=sample;
  306.             }
  307.             SetWindowPixelsQuickly((WindowPtr)world,rectPtr->left,y
  308.                 ,pix,rectPtr->right-rectPtr->left);
  309.         }
  310.         actualMean=a/n;
  311.         actualSd=sqrt(aa/n-actualMean*actualMean);
  312.         if(diagnostics)printf("unclippedSd %f, actualSd %f, actualSd/unclippedSd %f, n %ld\n"
  313.             ,*sdPtr,actualSd,actualSd/(*sdPtr),n);
  314.         break;
  315.     default:
  316.         PrintfExit("%s,%d: No such pdf %d\n",__FILE__,__LINE__,(int)pdfKind);
  317.     }
  318.     if(diagnostics){
  319.         ImageStatistics(world,rectPtr,&actualMin,&actualMax,&actualMean,&meanSquare);
  320.         if(actualMax>max || actualMin<min)printf("\nIMAGE OVERFLOW ERROR:\n");
  321.         printf("noise actualMin %ld≥%d, actualMax %ld≤%d, actualMean %.1f≈%.1f, rms %.1f≈%.1f≈%.1f\n"
  322.             ,actualMin,(int)min
  323.             ,actualMax,(int)max
  324.             ,actualMean,*meanPtr
  325.             ,sqrt(meanSquare),actualSd,*sdPtr);
  326.         assert(actualMax<=max && actualMin>=min);
  327.     }
  328. done:
  329.     *sdPtr=actualSd;
  330.     *meanPtr=actualMean;
  331.     return error;
  332. }
  333.  
  334. OSErr NoisePdfAdd(GWorldPtr world,Rect *rectPtr
  335.     ,int pdfKind,double *meanPtr,double *sdPtr,int min,int max)
  336. {
  337.     GWorldPtr noiseWorld;
  338.     GDHandle device;
  339.     int error=0,pixelSize,id;
  340.     double meanSquare,actualMean;
  341.     long actualMin,actualMax;
  342.     ColorTable **ct;
  343.     long copyMode;
  344.  
  345.     assert(world!=NULL);
  346.     device=GetWindowDevice((WindowPtr)world);
  347.     id=pixelSize=(**(**device).gdPMap).pixelSize;
  348.     if(id>2)id+=32;
  349.     ct=GetCTable(id);    // gray ramp
  350.     assert(ct!=NULL);
  351.     error=NewGWorld(&noiseWorld,pixelSize,rectPtr,ct,0,0);
  352.     if(error)error=NewGWorld(&noiseWorld,pixelSize,rectPtr,ct,0,useTempMem);
  353.     if(error)return error;
  354.     error=NoisePdfFill(noiseWorld,rectPtr,pdfKind,meanPtr,sdPtr,min,max);
  355.     if(error)goto done;
  356.     if(min>=0)copyMode=addOverParallelLiterally;    // no overflow
  357.     else copyMode=addOver;                            // "sign" bit may overflow
  358.     error=CopyWindows(noiseWorld,world,rectPtr,rectPtr,copyMode,NULL);
  359.     if(error)PrintfExit("%s line %d: CopyWindows error %d\n",__FILE__,__LINE__,error);
  360.     if(diagnostics){
  361.         ImageStatistics(world,&world->portRect,&actualMin,&actualMax,&actualMean,&meanSquare);
  362.         if(actualMax>max || actualMin<min || diagnostics){
  363.             printf("signal+noise actualMin %ld, actualMax %ld, actualMean %.1f, actualSd %.1f\n"
  364.                 ,actualMin,actualMax,actualMean,sqrt(meanSquare-actualMean*actualMean));
  365.         }
  366.     }
  367. done:
  368.     DisposeGWorld(noiseWorld);
  369.     return error;
  370. }
  371.  
  372. void GetGoodNoisePdfBounds(int pdfKind,double mean,double clippedSd
  373.     ,double *unclippedSdPtr,int *minPtr,int *maxPtr)
  374. {
  375.     double dMax,dMin,clippedSd1;
  376.     int low,high;
  377.     
  378.     assert(unclippedSdPtr!=NULL && minPtr!=NULL && maxPtr!=NULL);
  379.     assert(clippedSd>=0);
  380.     assert(*maxPtr>=*minPtr);
  381.     
  382.     // dMax,dMin,clippedSd1
  383.     switch(pdfKind){
  384.     case kBinaryPdf:
  385.         dMax=clippedSd;
  386.         dMin=-dMax;
  387.         clippedSd1=1;
  388.         break;
  389.     case kUniformPdf:
  390.         dMax=sqrt(3)*clippedSd-0.5;
  391.         dMin=-dMax;
  392.         clippedSd1=1;
  393.         break;
  394.     case kBinomialPdf:
  395.         dMax=2*clippedSd;
  396.         dMin=-dMax;
  397.         clippedSd1=0.85;
  398.         break;
  399.     case kGaussianPdf:
  400.         dMax=2*clippedSd;
  401.         dMin=-dMax;
  402.         clippedSd1=0.737;
  403.         break;
  404.     }
  405.     // high and low are the extremes of the pdf.
  406.     // The high-low difference is more important than the absolute value of either.
  407.     assert(dMax>=dMin);
  408.     low=MAX(floor(0.5+mean+dMin),*minPtr);
  409.     high=MIN(floor(0.5+low+(dMax-dMin)),*maxPtr);
  410.     low=MAX(floor(0.5+high-(dMax-dMin)),*minPtr);
  411.     if(low==high && clippedSd>0){
  412.         if(high<*maxPtr)high++;
  413.         else if(low>*minPtr)low--;
  414.     }
  415.     *minPtr=low;
  416.     *maxPtr=high;
  417.     *unclippedSdPtr=clippedSd/clippedSd1;
  418. }